﻿//#include <iostream>
//using namespace std;
//typedef struct BTnode
//{
//    char data;
//    struct BTnode* left;
//    struct BTnode* right;
//}BTnode;
//BTnode* buytree(char x)
//{
//    BTnode* node = new BTnode;
//    node->data = x;
//    node->left = NULL;
//    node->right = NULL;
//    return node;
//}
////二叉树查找值为x的结点
//BTnode* findnode(BTnode* root, char x)//注意返回值是BTnode*
//{
//    if (root == NULL)
//        return NULL;
//    else
//    {
//        if (root->data == x)
//        return root;
//        BTnode* lresult = findnode(root->left, x);
//        if(lresult)
//            return findnode(root->left, x);
//        BTnode* rresult = findnode(root->right, x);
//        if (rresult)
//            return findnode(root->right, x);
//        return NULL;
//    }
//}
//int main()
//{
//    std::cout << "Hello World!\n";
//}
//
#include <iostream>
#include <string>
#include <queue>
using namespace std;
class BTNode
{
public:
	char data;
	BTNode* left;
	BTNode* right;
	BTNode()
	{
		left = NULL;
		right= NULL;
	}
	BTNode(char x)
	{
		data = x;
		left = NULL;
		right = NULL;
	}
	BTNode* createtree(string str, int* i)
	{
		if (str[*i] == '#')
		{
			(*i)++;
			return NULL;
		}
		else
		{
			BTNode* root =new BTNode(str[*i]);
			root->data=str[(*i)++];
			root->left=createtree(str, i);
			root->right = createtree(str, i);
			return root;
		}
	}
	BTNode* intree(BTNode* root)
	{
		if (root == NULL)
			return NULL;
		else
		{
			intree(root->left);
			cout << root->data << " ";
			intree(root->right);
			return root;
		}
	}
	void Destroy(BTNode* root)
	{
		if (root == NULL)
			return;
		else
		{
			Destroy(root->left);
			Destroy(root->right);
			delete root;
		}
	}
	void leveltree(BTNode* root)
	{
		if (root == NULL)
			return;
		else
		{
			queue<BTNode*>q;
			q.push(root);
			while (!q.empty())
			{
				BTNode* node = q.front();
				q.pop();
				cout << node->data << " ";
				if (node->left)
				{
					q.push(node->left);
				}
				if (node->right)
				{
					q.push(node->right);
				}
			}
		}
	}
	void leveltree(BTNode* root)
	{
		if (root == NULL)
			return;
		else
		{
			BTNode* queue[1000];
			int front = 0;//队首
			int rear = 0;//队尾进入
			queue[rear++] = root;
			while (front < rear)
			{
				BTNode* node = queue[front++];
				cout << node->data << " ";
				if (node->left)
				{
					queue[rear++]=node->left;
				}
				if (node->right)
				{
					queue[rear++]=node->right;
				}
			}
		}
	}
	void leveltree(BTNode* root)
	{
		if (root == NULL)
			return;
		else
		{
			BTNode* queue[2000];
			int front = 0;
			int rear = 0;
			queue[rear++] = root;
			while (front < rear)
			{
				BTNode* node = queue[front++];
				cout << node->data << " ";
				if (node->left)
				{
					queue[rear++] = node->left;
				}
				if (node->right)
				{
					queue[rear++] = node->right;
				}
			}
		}
	}
};
int main()
{
	string str;
	cin >> str;
	BTNode node;
	int i = 0;
	BTNode* root=node.createtree(str, &i);
	node.intree(root);
	node.Destroy(root);
	return 0;
}